package com.cqs.leetcode;

/**
 * 缺点 不能处理 大型数组
 * leetcode 会出现超时
 * quick-find 实现
 * Created by cqs on 2018/4/3.
 */
public class NumberOfIslands2 {

    private int row;
    private int cell;
    private int[] ids;

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        this.row = grid.length;
        this.cell = grid[0].length;
        int count = row * cell;
        ids = new int[count];
        //时间复杂度N的四次方
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < cell; j++) {
                int idx = index(i, j);
                //找到对应的集合
                if (grid[i][j] == '1') {
                    ids[idx] = idx;
                    //正北节点也是'1' 说明是同一个集合  更新当前点所在的集合
                    if (i > 0 && grid[i - 1][j] == '1') {
                        ids[idx] = find(i - 1, j);
                        --count;
                    }
                    //和紧临的左兄弟节点所在集合进行union
                    if (j > 0 && grid[i][j - 1] == '1') {
                        int id = find(i, j - 1);
                        if (id != ids[idx]) {//union
                            union(i, j);
                            --count;
                        }
                    }
                } else {
                    ids[idx] = -1;
                    --count;
                }
            }
        }
        return count;
    }

    //返回的是
    private int find(int i, int j) {
        return ids[index(i, j)];
    }


    //大型数组 时间复杂度太高
    private void union(int i, int j) {
        int tmp = ids[index(i, j - 1)];
        int index0 = index(i, j);
        //每次均要扫描一遍 时间复杂度太高了
        for (int k = 0; k <= index0; k++) {
            if (ids[k] == ids[index0]) {
                ids[k] = tmp;
            }
        }
    }

    private int index(int i, int j) {
        return i * cell + j;
    }

}
